package pro.softzhang.algo.lc200;


import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;
import pro.softzhang.algo.flag.x.XOptimal;

@KDynamicPlanning
@DRed
public class LC256_PaintHouse {
    public static void main(String[] args) {
//        int[][] costs = new int[][]{{17,2,17},{16,16,5},{14,3,19}};
        int[][] costs = new int[][]{{3,5,3},{6,17,6},{7,13,18},{9,10,18}};
        int minCost = new Solution().minCost(costs);
        System.out.println(minCost);
    }

    @XOptimal
    static class Solution {
        public int minCost(int[][] costs) {
            int[][] dp = new int[3][2];
            for (int i = 0; i < 3; i++) {
                dp[i][0] = costs[0][i];
            }

            for (int i = 1; i < costs.length; i++) {
                for (int j = 0; j < 3; j++) {
                    int p1 = dp[(j + 1) % 3][(i - 1) % 2];
                    int p2 = dp[(j + 2) % 3][(i - 1) % 2];
                    dp[j % 3][i % 2] = Math.min(p1, p2) + costs[i][j];
                }
            }
            int idx = (costs.length - 1) % 2;
            return Math.min(dp[0][idx], Math.min(dp[1][idx], dp[2][idx]));
        }
    }
}